package shortestpath;

/**
 * 单源最短路径
 *
 * @author zj
 */
public class ShortestPath {
    public static int INF = 1000;
    public static int A[][] = {
            {0, 4, 6, 6, INF, INF, INF},
            {INF, 0, 1, INF, 7, INF, INF},
            {INF, INF, 0, INF, 6, 4, INF},
            {INF, INF, 2, 0, INF, 5, INF},
            {INF, INF, INF, INF, 0, INF, 6},
            {INF, INF, INF, INF, 1, 0, 8},
            {INF, INF, INF, INF, INF, INF, 0}
    };

    public static void shortestPath(int[][] A, int v0) {
        int length = A.length;
        int dist[] = new int[length]; //记录当前最短路径
        int path[] = new int[length]; //记录最短路径上的前一个顶点
        boolean flag[] = new boolean[length]; //记录是否找到最短路径

        for (int i = 0; i < length; i++) { //初始化
            dist[i] = A[v0][i];
            flag[i] = false;
            if (A[v0][i] < INF)
                path[i] = v0;
            else
                path[i] = -1;  //表示源点到顶点vi无路径
        }

        flag[v0] = true; //首先，源点标记为已求出最短距离
        path[v0] = 0;

        for (int i = 0; i < length; i++) {
            int currentMin = INF;
            int currentIndex = 0;
            for (int j = 0; j < length; j++) {
                if (flag[j] == false && dist[j] < currentMin) {
                    currentIndex = j;
                    currentMin = dist[j];
                }
            }
            flag[currentIndex] = true;
            for (int j = 0; j < length; j++) {
                if (flag[j] == false) {
                    if (A[currentIndex][j] < INF && dist[currentIndex] + A[currentIndex][j] < dist[j]) {
                        dist[j] = dist[currentIndex] + A[currentIndex][j];
                        path[j] = currentIndex;
                    }
                }
            }
        }

        dispath(dist, path, flag, length, v0);
    }

    public static void path(int path[], int i, int v0) {
        int k = path[i];
        if (k == v0) {
            System.out.print("【" + k + "】-->");
            return;
        }
        path(path, k, v0);
        System.out.print("【" + k + "】-->");
    }

    public static void dispath(int dist[], int path[], boolean flag[], int length, int v0) {
        for (int i = 0; i < length; i++) {
            if (i == v0) continue;
            if (flag[i] == true) {
                System.out.println("从顶点【" + v0 + "】到顶点【" + i + "】的最短路径为：" + dist[i]);
                System.out.print("路径：");
                path(path, i, v0);
                System.out.println("【" + i + "】\n");
            } else {
                System.out.println("从顶点【" + v0 + "】到顶点【" + i + "】不存在路径！\n");
            }
        }
    }

    public static void main(String[] args) {
        shortestPath(A, 0);
    }
}
